package com.fulin.datastract.tree;

import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.Setter;

/**
*
* @description 二叉搜索树,可能是不平衡的
* @auther fulin16@crnet.com.hk
* @since 2020年6月22日 下午5:38:02
*
*/

@Setter
@Getter
@AllArgsConstructor
@NoArgsConstructor
public class BSTree {

	private Node root;
	
	public void insert(int v) {
		if(root == null) {
			root = new Node(v,null,null);
			return;
		}
		
		
		Node node = root;
		while(node != null) {
			int val = node.getVal();
			if(v < val) {
				if(node.getLeft() == null) {
					node.setLeft(new Node(v,null,null));
					return;
				}
				node = node.getLeft();
			}else if(val < v) {
				if(node.getRight() == null) {
					node.setRight(new Node(v,null,null));
					return;
				}
				node = node.getRight();
			}else {
				System.out.println("已经存在此元素，将忽略");
			}
		}
	}
	
	public void loopBST() {
		loop(root);
	}
	
	private void loop(Node node) {
		if(node == null) {
			return;
		}
		loop(node.getLeft());
		System.out.print(node.getVal() + " - ");
		loop(node.getRight());
	}
	
	public static void main(String[] args) {
		int[] vals = {2,8,7,9,23,21,45,78,1,10};
		BSTree bst = new BSTree();
		for(int i = 0; i< vals.length ; i++) {
			bst.insert(vals[i]);
		}
		
		bst.loopBST();
		
		System.out.println("root => " + bst.getRoot().getVal());
	}
}
